package sstable

import (
	"lsmtree/kv"
	"sync"
)

/*

LSM Tree（Log-Structured Merge Tree）是一种用于存储和管理大量数据的高效数据结构，特别适用于写密集型的应用场景。它通过将数据分段存储在不同的层次结构中，并通过合并操作来管理这些数据段，从而优化了写入和读取操作。以下是对LSM Tree的详细介绍：
LSM Tree的基本概念
LSM Tree由多个层次的组件组成，每个组件存储一定范围的键值对。最底层的组件通常驻留在内存中，而其他组件则驻留在磁盘上。LSM Tree的主要组件包括：
MemTable：这是一个驻留在内存中的数据结构，用于存储最新的写入操作。当MemTable达到一定大小时，它会被写入磁盘，形成一个新的SSTable。
Immutable MemTable：当MemTable满时，它会变成Immutable MemTable，等待被刷到磁盘。
SSTable（Sorted String Table）：这是一种驻留在磁盘上的有序数据结构，用于存储从MemTable刷下来的数据。SSTable是不可变的，这意味着一旦写入磁盘，它们不会被修改。
写入操作
写入MemTable：当有新的数据写入时，数据首先被写入MemTable。
生成SSTable：当MemTable满时，它会被转换为Immutable MemTable，并异步地被写入磁盘，形成一个新的SSTable。
WAL（Write-Ahead Log）：为了保证数据的可靠性，每次写入操作还会记录到WAL中，以防止数据丢失。
读取操作
从MemTable读取：读取操作首先在MemTable中查找数据。
从Immutable MemTable读取：如果未找到数据，则继续在Immutable MemTable中查找。
从SSTable读取：如果仍未找到数据，则在磁盘上的SSTable中查找。
合并操作
为了避免SSTable数量过多导致读取性能下降，LSM Tree会定期执行合并操作，将多个SSTable合并成一个新的SSTable。这种合并操作分为两种策略：
Leveling：每一层只有一个SSTable，当一层满时，将其合并到下一层。
Tiering：每一层可以有多个SSTable，当一层满时，将所有SSTable合并成一个新的SSTable，并移动到下一层。

*/

/*

   +----------------------+
   |      Write-Ahead Log |
   +----------------------+
             |
             v
   +----------------------+
   |       MemTable       |
   +----------------------+
             |
             v
   +----------------------+
   | Immutable MemTable   |
   +----------------------+
             |
             v
   +----------------------+
   |       SSTable        |
   +----------------------+
             |
             v
   +----------------------+
   |       Compaction     |
   +----------------------+
             |
             v
   +----------------------+
   |       SSTable        |
   +----------------------+

*/

/*
LSM Tree 的数据结构
LSM Tree由以下数据结构组成：
TableTree：这是根节点的 TableNode 列表，用于管理 SSTable 并提供查询操作。
TableNode：这是 SSTable 的节点，包含 SSTable 实例、指向下一层 TableNode 的指针。
SSTable：这是留在磁盘上的有序数据结构，用于存储键值对。
MemTable：这是留在内存中的数据结构，用于存储最新的写入操作。

LSMTree

		MemTable | MemTable | MemTable | MemTable
							|
							V
		IMemTable | IMemTable | IMemTable | IMemTable
							|
		                    V
		TableTree
		-------------------------------------------------------------
		｜															|
		｜ level0: SSTable											|
		｜															|
		｜ level1: SSTable->SSTable->SSTable						|
		｜														    |
		｜ level2: SSTable->SSTable->SSTable->SSTable				|
		｜															|
		｜....................										|
		｜															|
		｜ level10: SSTable->SSTable->SSTable->SSTable->SSTable		|
		-------------------------------------------------------------



*/

type TableNode struct {
	index uint32
	table *SSTable
	next  *TableNode
}

type TableTree struct {
	levels []*TableNode
	lock   *sync.RWMutex
}

// 从所有 SSTable 中查找数据
func (tree *TableTree) Search(key string) (kv.Value, kv.SearchResult) {
	tree.lock.RLock()
	defer tree.lock.RUnlock()

	// 依次遍历每一层的 SSTable
	for _, node := range tree.levels {
		tables := make([]*SSTable, 0)
		for node != nil {
			tables = append(tables, node.table)
			node = node.next
		}

		for i := len(tables) - 1; i >= 0; i-- {
			value, searchResult := tables[i].Search(key)
			if searchResult == kv.None {
				continue
			} else {
				return value, searchResult
			}
		}
	}

	return kv.Value{}, kv.None
}

func (tree *TableTree) getMaxIndex(level int) uint32 {
	node := tree.levels[level]
	var index uint32 = 0
	for node != nil {
		index = node.index
		node = node.next
	}
	return index
}

func (tree *TableTree) getCount(level int) uint32 {
	node := tree.levels[level]
	var count uint32 = 0
	for node != nil {
		count++
		node = node.next
	}
	return count
}
